和 拥有共同的 级祖先的点数就是 的 级祖先的 级儿子的数量 .
再转换一下就是以 的 级祖先为根的子树内深度为 的点的个数。
然后用 表示深度为 的点数,直接 即可。
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1e5 , MAXK = 20;
int n , m , col[ MAXN + 5 ];
struct Query{ int id , dep; };
vector< Query > Qry[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
int dep[ MAXN + 5 ] , Size[ MAXN + 5 ] , Son[ MAXN + 5 ];
int Anc[ MAXN + 5 ][ MAXK + 5 ];
void dfs1( int u , int fa ) {
dep[ u ] = dep[ fa ] + 1 , Size[ u ] = 1;
Anc[ u ][ 0 ] = fa;
for( int i = 1 ; i <= MAXK ; i ++ ) Anc[ u ][ i ] = Anc[ Anc[ u ][ i - 1 ] ][ i - 1 ];
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs1( v , u ); Size[ u ] += Size[ v ];
if( Size[ Son[ u ] ] < Size[ v ] ) Son[ u ] = v;
}
}
int Cnt[ MAXN + 5 ];
int Ans[ MAXN + 5 ] , Sonu;
void Count( int u , int fa , int val ) {
Cnt[ dep[ u ] ] += val;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa || v == Sonu ) continue;
Count( v , u , val );
}
}
bool vis[ MAXN + 5 ];
void dfs2( int u , int fa , bool is_hs ) {
vis[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa || v == Son[ u ] ) continue;
dfs2( v , u , 0 );
}
if( Son[ u ] ) dfs2( Son[ u ] , u , 1 );
Sonu = Son[ u ]; Count( u , fa , 1 ); Sonu = 0;
for( int i = 0 ; i < Qry[ u ].size() ; i ++ ) Ans[ Qry[ u ][ i ].id ] = Cnt[ dep[ u ] + Qry[ u ][ i ].dep ] - 1;
if( !is_hs ) Count( u , fa , -1 );
}
int main( ) {
scanf("%d",&n);
for( int i = 1 , fa ; i <= n ; i ++ ) {
scanf("%d",&fa);
Graph[ fa ].push_back( i );
}
for( int i = 1 ; i <= n ; i ++ )
if( !dep[ i ] ) dfs1( i , 0 );
scanf("%d",&m);
for( int i = 1 , rt , k ; i <= m ; i ++ ) {
scanf("%d %d",&rt,&k);
for( int i = 0 ; i <= MAXK ; i ++ ) if( ( k >> i ) & 1 ) rt = Anc[ rt ][ i ];
Qry[ rt ].push_back( { i , k } );
}
for( int i = 1 ; i <= n ; i ++ )
if( !vis[ i ] ) dfs2( i , 0 , 0 );
for( int i = 1 ; i <= m ; i ++ )
printf("%d ", Ans[ i ] );
return 0;
}
再说说这道题的加强版 P5384 [Cnoi2019]雪松果树。
出题人卡了空间,正常写法只有 40 pts。
首先倍增数组太占空间,考虑离线求出 级祖先。
时可以用栈维护根到当前节点的路径上的点。
那么它的 级祖先就应该是栈中的第 个元素。
然后你就多得了 4 pts 了。
将 改成链表,再卡卡常就可以过了。
虽然正解是长链剖分